package Algorithm.String;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Leetcode1044_notice_最长重复字串 {
    /**
     * 自己写的，but 超时了
     */
    class Solution {
        Map<String, Integer> map = new HashMap<String, Integer>();

        public String longestDupSubstring(String s) {
            //分为两步骤
            //1.找出匹配串 2.从s中找到匹配串的个数
            //在挑选匹配串的时候，考虑s的所有子串肯定不行
            //但是注意到一个性质，就是当固定i为开头，然后增加j的位置增加子串的长度时，
            //如果重复个数下降了，那么继续增加长度也没用
            //再用 map 剪枝已经搜过的子串

            int i = 0;
            int max = 0;
            String result = "";

            for(int j = 1; j <= s.length(); j++){
                String target = s.substring(i+1, s.length());
                // String target = s.substring(i, s.length());
                String partten = s.substring(i, j);
                int num = 0;
                if((num = map.getOrDefault(partten, -1)) < 0){
                    num = findRepeatedNums(target, partten);
                    map.put(partten, num);
                    while(num < 1 && i < j){
                        i++;
                        target = s.substring(i, s.length());
                        partten = s.substring(i, j);
                        if((num = map.getOrDefault(partten, -1)) < 0){
                            num = findRepeatedNums(target, partten);
                            map.put(partten, num);
                        }
                    }
                }

                if(j - i > max){
                    result = s.substring(i, j);
                }
                max = Math.max(max, j-i);
            }

            return result;
        }

        public int findRepeatedNums(String target, String partten){
            int index = target.indexOf(partten);
            if(index != -1){
                return 1;
            }
            return 0;
        }
    }


    /**
     * 二分查找 + Rain-Karp
     */
    class Solution2 {
        public String longestDupSubstring(String s) {
            int l = 0 ;
            int r = s.length()-1;
            String result = "";
            String ans = "";
            while(l <= r){
                int mid = (l + r + 1) / 2;
                result = find(s, mid);
                if(!result.equals("")){
                    l = mid + 1 ;
                    ans =  result;
                }else{
                    r = mid - 1;
                }
            }

            return ans;
        }

        public String find(String s, int len){
            Set<Long> set = new HashSet<Long>();
            //自定义 hash
            int h = 31;
            long hashCode = 0;
            long power = 1;
            for(int i = 0 ;i < len; i++){
                hashCode = hashCode * h + s.charAt(i);
                power = power * h;
            }
            set.add(hashCode);

            for(int i = len;i < s.length(); i++){
                hashCode = hashCode * h + s.charAt(i) - power * s.charAt(i - len);
                String ans;
                if(set.contains(hashCode) ){
                    return s.substring(i-len+1,i+1);
                }
                set.add(hashCode);
            }

            return "";
        }

    }
}
